Langford Pairs – a silly hill climber
Langford pairs are sequences if numbers where each number less than n occurs twice, and each occurrence of a value (i) is separated by i other numbers. For example for n=3:
3 1 2 1 3 2So there you go. It’s a largely theoretical problem, though I think such sequences could have practical applications. For example, say you have a black box, caesar cypher encoder. You can feed it strings and look at the output in order to determine the substitution matrix being used… However the encoder embeds the message with a random amount of padding, and randomly discards parts of you message… Feeding the encoder a Langford pair may be an efficient way to determine the substitution matrix. Once encoded you can simply see which pairs are a given distance apart, the distance gives you the symbol number…
Anyway.
This is a silly hill climber for finding Langford pairs. There are surely better algorithms for doing this, and hill climbers don’t work particularly well! (solutions were at best 1 off for langford pairs beyond n=3. But I wonder what it is about the landscape that makes hill climbers perform badly here. As it’s almost a toy problem it might be interesting to play with a little.
import random
size = 7
def langfordscore(l):
score = 0
for i in range(1,size):
idx = []
for j in range(len(l)):
if(l[j] == i):
idx.append(j)
if (abs(idx[0]-idx[1]) != (i+1)):
score = score+1
return score
def swap(l):
i = random.randint(0,len(l)-1)
j = random.randint(0,len(l)-1)
nl = list(l)
nl[i] = l[j]
nl[j] = l[i]
return nl
langford = []
for i in range(1,size):
langford.append(i)
langford.append(i)
print langford
score = 1000
ittr = 0
lastmove = 0
mutrate = 0
while ((score != 0) and (ittr < 200000)):
nlangford = swap(langford)
for i in range(mutrate):
nlangford = swap(nlangford)
if (lastmove > 500):
lastmove = 0
mutrate = mutrate + 1
if (mutrate > 5):
mutrate = 0
nscore = langfordscore(nlangford)
if(nscore < score):
langford = nlangford
score = nscore
print score
print langford
else:
lastmove = lastmove + 1
ittr = ittr + 1
RSS